package com.sjc.algorithm.tree;

import java.util.Arrays;

/**
 * 优先队列
 * 最小堆
 * @author by SangJiacun
 * @Date 2020/5/11 16:50
 */
public class PriorityQueue {
    private int[] array;
    private int size;

    public PriorityQueue(){
        array = new int[32];
    }

    /**
     * 入队
     * @param data 插入的数据
     */
    public void enQueue(int data){
        if(size >= array.length){
            resize();
        }
        array[size++] = data;
        upAdjuct();
    }

    /**
     * 入队：元素上浮
     */
    public void upAdjuct(){
        int child = size-1;
        int parent = (child-1)/2;

        int temp = array[child];

        while(child>0 && temp < array[parent]){
            array[temp] = array[parent];
            child = parent;
            parent = (parent-1)/2;
        }
        array[child] = temp;
    }

    /**
     *  出队
     * @return 返回的数据
     * @throws Exception
     */
    public int deQueue() throws Exception {
        if(size <=0){
            throw new Exception("队列为空!");
        }

        int head = array[0];
        array[0] = array[--size];
        downAdjuct();
        return head;
    }

    /**
     * 出队：元素下沉
     */
    public void downAdjuct(){
        int parent = 0;
        int temp = array[parent];
        int child = 1;
        while(child < size){
            // 如果有右孩子，且右孩子的值 小于 左孩子
            if(child+1 < size && array[child+1] < array[child]){
                child++;
            }

            if(temp <= array[child]){
                break;
            }

            array[parent] = array[child];
            parent = child;
            child = parent*2 +1;
        }
        array[parent] = temp;
    }

    /**
     * 队列扩容
     */
    public void resize(){
        int newSize = this.size *2;
        this.array = Arrays.copyOf(array, newSize);
    }

    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        System.out.println("出队元素: "+priorityQueue.deQueue());
        System.out.println("出队元素: "+priorityQueue.deQueue());
    }
}
